package main.java.indi.zyj.c150.bfs;

import java.util.*;

public class _02_OpenLock {

    public int openLock(String[] deadends, String target) {
        return BFS(deadends, target);
    }

    int BFS(String[] deadends, String target){

        String init = "0000";
        int dpth = 0;
        Queue<String> treeNodeQueueueue = new LinkedList<>();

        Set<String> visited = new HashSet<>();

        Set<String> deads = new HashSet<>();
        for (String s : deadends) {
            deads.add(s);
        }

        treeNodeQueueueue.offer(init);
        visited.add(init);

        while (!treeNodeQueueueue.isEmpty()){

            int size = treeNodeQueueueue.size();
            for (int i = 0; i < size; i++) {
                String curLock = treeNodeQueueueue.poll();

                if (deads.contains(curLock)){
                    continue;
                }
                if (curLock.equals(target)){
                    return dpth;
                }

                for (int j = 0; j < 4; j++) {
                    String plus = plusOne(curLock, j);
                    if (!visited.contains(plus)){
                        treeNodeQueueueue.offer(plus);
                        visited.add(plus);
                    }
                    String minus = minusOne(curLock, j);
                    if (!visited.contains(minus)){
                        treeNodeQueueueue.offer(minus);
                        visited.add(minus);
                    }
                }
            }
            dpth++;
        }
        return -1;
    }

    public String plusOne(String s, int j){
        char[] chars = s.toCharArray();
        if (chars[j] == '9'){
            chars[j] = '0';
        }else {
            chars[j] += 1;
        }
        return new String(chars);
    }
    public String minusOne(String s, int j){
        char[] chars = s.toCharArray();
        if (chars[j] == '0'){
            chars[j] = '9';
        }else {
            chars[j] -= 1;
        }
        return new String(chars);
    }

}
